package com.lw.leetcode.binary.b;

/**
 * Created with IntelliJ IDEA.
 * 1802. 有界数组中指定下标处的最大值
 * b
 * biany
 *
 * @author liw
 * @version 1.0
 * @date 2023/1/4 9:31
 */
public class MaxValue {

    public int maxValue(int n, int index, int maxSum) {
        long st = 1;
        long end = maxSum;
        while (st < end) {
            long m = st + ((end - st + 1) >> 1);
            long l = index;
            long r = n - 1 - index;
            if (l < m) {
                l = (m + m - 1 - l) * l >> 1;
            } else {
                l = ((m - 1) * m >> 1) + l - m + 1;
            }
            if (r < m) {
                r = (m + m - 1 - r) * r >> 1;
            } else {
                r = ((m - 1) * m >> 1) + r - m + 1;
            }
            long s = l + r + m;
            if (s <= maxSum) {
                st = m;
            } else {
                end = m - 1;
            }
        }
        return (int) st;
    }

}
